package main

import "fmt"

//
//  ListNode
//  @Description: 链表数据结构的定义
//
type ListNode struct {
	Val  int
	Next *ListNode
}

// reverseList
// @Description: 就地翻转单链表
// @param head
// @return *ListNode
func reverseList(head *ListNode) *ListNode {
	if head == nil {
		return nil
	}
	var slow *ListNode
	fast := head
	for head != nil {
		fast = head.Next
		head.Next = slow
		slow = head
		head = fast
	}
	return slow
}

// reverseList2
// @Description: 使用栈实现
// @param head
// @return *ListNode
func reverseList2(head *ListNode) *ListNode {
	if head == nil {
		return nil
	}
	myStack := []*ListNode{}
	for cur := head; cur != nil; {
		temp := cur
		cur = cur.Next
		temp.Next = nil
		myStack = append(myStack, temp)

	}
	root := &ListNode{}
	cur := root
	for len(myStack) > 0 {
		root.Next = myStack[len(myStack)-1]
		myStack = myStack[:len(myStack)-1]
		root = root.Next
	}
	return cur.Next
}

// reverseList3
// @Description: 使用递归实现
// @param head
// @return *ListNode
func reverseList3(head *ListNode) *ListNode {
	if head == nil || head.Next == nil {
		return head
	}
	newHead := reverseList(head.Next)
	head.Next.Next = head
	head.Next = nil
	return newHead
}
func display(head *ListNode) []int {
	if head == nil {
		return nil
	}
	var ans []int
	for cur := head; cur != nil; cur = cur.Next {
		ans = append(ans, cur.Val)
	}
	return ans
}
func main() {
	test := &ListNode{
		Val: 1,
		Next: &ListNode{
			Val: 2,
			Next: &ListNode{
				Val: 3,
				Next: &ListNode{
					Val: 4,
					Next: &ListNode{
						Val:  5,
						Next: nil,
					},
				},
			},
		},
	}
	fmt.Println(display(test))
	test = reverseList2(test)
	fmt.Println(display(test))
}
